#include <bits/stdc++.h>

#define in read()
#define fi first
#define se second
#define pb push_back
#define rep(i, x, y) for(int i = (x); i <= (y); i++) 
#define per(i, x, y) for(int i = (x); i >= (y); i--)

using namespace std;

using ll = long long;
using db = double;
using pii = pair < int , int >;
using vec = vector < int >;
using veg = vector < pii >;

int read() {
	int x = 0; bool f = 0; char ch = getchar(); while(!isdigit(ch)) f |= ch == '-', ch = getchar(); 
	while(isdigit(ch)) x = x * 10 + (ch ^ 48), ch = getchar(); return f ? -x : x;
}

const int N = 1e6 + 10;

ll ans[N];
int n, m;

namespace T {
	ll tr[N];
	void add(int x, int v) { for(; x <= m; x += x & -x) tr[x] += v; }
	ll query(int x) { ll res = 0; for(; x; x -= x & -x) res += tr[x]; return res; }
	ll query(int x, int y) { return query(y) - query(x - 1); }
	int get(int x) {
		ll t = query(x); int pos = 0;
		per(i, 18, 0)
			if((pos | 1 << i) <= x && tr[pos | 1 << i] < t) {
				pos |= 1 << i; t -= tr[pos];
			}
		return pos + 1;
	}
}

struct Tree {
	int fa[N], id[N], ch[N][2], tot, sz[N];
	Tree(int n = 0) { rep(i, 1, n) fa[i] = 0, id[i] = i, sz[i] = 1; tot = n; }
	void merge(int x, int y) {
		++tot; ch[tot][0] = id[x]; ch[tot][1] = id[y]; sz[tot] = sz[id[x]] + sz[id[y]];
		fa[id[x]] = tot; fa[id[y]] = tot; id[x] = tot;
	}
} t1, t2;

vec modi1[N], modi2[N], qry[N];
int lf[N];

void dfs1(int x) {
	for(auto v : modi2[x]) T :: add(v, 1);
	if(x <= n) {
		for(auto v : qry[x]) lf[v] = T :: get(v);
	} else dfs1(t2.ch[x][0]), dfs1(t2.ch[x][1]);
	for(auto v : modi2[x]) T :: add(v, -1);
}

void dfs2(int x) {
	for(auto v : modi1[x]) T :: add(v, t1.sz[x]);
	if(x <= n) {
		for(auto v : qry[x]) ans[v] = T :: query(lf[v], v);
	} else dfs2(t1.ch[x][0]), dfs2(t1.ch[x][1]);
	for(auto v : modi1[x]) T :: add(v, -t1.sz[x]);
}

int main() {
#ifndef ONLINE_JUDGE
	freopen("1.in", "r", stdin);
#endif
	n = in, m = in; t1 = Tree(n), t2 = Tree(n); 
	rep(i, 1, m) {
		char op = getchar(); while(!isalpha(op)) op = getchar();
		ans[i] = -1;
		if(op == 'U') { int a = in, b = in; t1.merge(a, b); }
		else if(op == 'M') { int a = in, b = in; t2.merge(a, b); }
		else if(op == 'A') { int a = in; modi1[t1.id[a]].pb(i); }
		else if(op == 'Z') { int a = in; modi2[t2.id[a]].pb(i); }
		else { int a = in; qry[a].pb(i); }
	}
	rep(i, 1, t2.tot) if(!t2.fa[i]) dfs1(i);
	rep(i, 1, t1.tot) if(!t1.fa[i]) dfs2(i);
	rep(i, 1, m) if(~ans[i]) printf("%lld\n", ans[i]);
	return 0;
}
